package sort

import (
    "fmt"
    "sort"
)

var Threshold int = 100

func SerialMerge(a, b, c Array) {

    i, j := 0,0
    // Merge
    for i < len(a) && j < len(b) {
        if a[i] < b[j] {
            c[i+j] = a[i]
            i++
        } else {
            c[i+j] = b[j]
            j++
        }
    }

    for i < len(a) {
        c[i+j] = a[i]
        i++
    }
    for j < len(b) {
        c[i+j] = b[j]
        j++
    }
}
func SerialMergeSort(a, b Array, start, stop int, src2dst bool) {
    if start==0 && stop==len(a) && false {
        fmt.Println("Sorting slice:\n", a)
    }
    //fmt.Println("Spawned [", start, "-", stop, "]")

    // Perform split unless size < 10
    if stop-start <= 10 {
        //sort.Sort(a[start:stop])
        //sort.Sort(b[start:stop])
        a.InsertionSort()
        b.InsertionSort()
        return
    }
    middle := start + (stop-start)/2
    // Sort each half
    SerialMergeSort(a, b, start, middle, !src2dst)
    SerialMergeSort(a, b, middle, stop, !src2dst)
    // Now merge
    src, dst := a, b
    if (!src2dst) {
        src, dst = dst, src
    }
    SerialMerge(src[start:middle], src[middle:stop], dst[start:stop])
}

// Parallel merge
func ParallelMerge(a, b, c Array, resp chan int) {
    if len(b) > len(a) {
        a,b = b,a
    }

    if len(c) < Threshold {
        SerialMerge(a, b, c)
        resp <- 1
        return
    }

    //fmt.Println("PM spawned on ", a, b)

    // Base case
    if len(c) == 1 {
        c[0] = a[0]
        resp <- 1
        //fmt.Println("Merge of ", a, b, "yielded ", c)
        return
    }

    // What if both inputs are len==1
    if len(a) == 1 {
        if a[0] < b[0] {
            c[0], c[1] = a[0], b[0]
        } else {
            c[0], c[1] = b[0], a[0]
        }
        //fmt.Println("Merge of ", a, b, "yielded ", c)
        resp <- 1
        return
    }

    mid_a := len(a)/2
    wait := make(chan int, 2)
    median := a[mid_a]
    // Find j such that median <= b[j]
    j := sort.Search(len(b),
                    func(j int) bool {
                        if j < len(b)-1 {
                            return b[j] >= median
                        }
                        return b[j] >= median
                    })
    go ParallelMerge(a[:mid_a], b[:j], c[:mid_a+j], wait)
    go ParallelMerge(a[mid_a:], b[j:], c[mid_a+j:], wait)
    // Wait for children
    <-wait
    <-wait

    // Signal that I have finished
    resp <- 1
    return
}

func MergeSort(a, b Array, start, stop int, src2dst bool, resp chan int) {
    if start==0 && stop==len(a) && false {
        fmt.Println("Sorting slice:\n", a)
    }
    //fmt.Println("Spawned [", start, "-", stop, "]")

    // Perform split unless size < 10
    if stop-start <= Threshold {
        sort.Sort(a[start:stop])
        sort.Sort(b[start:stop])
        resp <- 1
        return
    }
    wait := make(chan int, 2)
    middle := start + (stop-start)/2
    go MergeSort(a, b, start, middle, !src2dst, wait)
    go MergeSort(a, b, middle, stop, !src2dst, wait)
    // Wait for both to complete
    <-wait
    <-wait
    src, dst := a, b
    if (!src2dst) {
        src, dst = dst, src
    }
    SerialMerge(src[start:middle], src[middle:stop], dst[start:stop])
    resp <- 1
}
func ParallelMergeSort(a, b Array, start, stop int, src2dst bool, resp chan int) {
    if start==0 && stop==len(a) && false {
        fmt.Println("Sorting slice:\n", a)
    }
    //fmt.Println("Spawned [", start, "-", stop, "]")

    // Perform split unless size < 10
    if stop-start <= Threshold {
        sort.Sort(a[start:stop])
        sort.Sort(b[start:stop])
        resp <- 1
        return
    }
    wait := make(chan int, 2)
    middle := start + (stop-start)/2
    go ParallelMergeSort(a, b, start, middle, !src2dst, wait)
    go ParallelMergeSort(a, b, middle, stop, !src2dst, wait)
    // Wait for both to complete
    <-wait
    <-wait
    src, dst := a, b
    if (!src2dst) {
        src, dst = dst, src
    }
    ParallelMerge(src[start:middle], src[middle:stop], dst[start:stop], wait)
    <-wait
    resp <- 1
}
